package leetcode.code0864;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int m, n, limit, ans, size;
	int[] keys;
	char[][] g;

	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public int shortestPathAllKeys(String[] grid) {
		m = grid.length;
		n = grid[0].length();
		size = 0;
		keys = new int[6];
		g = new char[m][];
		// 初始化数组g，为了方便
		for (int i = 0; i < m; i++) {
			g[i] = grid[i].toCharArray();
		}
		int start = 0;
		// 找钥匙数量size，钥匙具体位置keys，起点start
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				char cur = g[i][j];
				if (cur >= 'a' && cur <= 'z') {
					keys[cur - 'a'] = index(i, j);
					size++;
				} else if (cur == '@') {
					start = index(i, j);
				}
			}
		}
		limit = (1 << size) - 1;
		// 从起点开始尝试，钥匙状态0
		return f(start, 0);// 从0位置开始，钥匙0
	}
	
	
	public int index(int i, int j) {
		return i * n + j;
	}

	private int f(int index, int key) {
		if (key == limit) {
			return 0;
		}
		int cur = Integer.MAX_VALUE;
		for (int i = 0; i < size; i++) {
			if ((key & (1 << i)) == 0) {//  尝试去每一个没有取到的钥匙
				int min = this.ff(index, keys[i], key);// 从当前钥匙index ，到目标钥匙keys[i]的最短距离
				if (min == -1) {// 不可达
					continue;
				}
				int next = this.f(keys[i], key | 1 << i);// 后续最短距离
				if (next != -1) {// 可达，收集答案
					cur = Math.min(cur, next + min);
				}
			}
		}
		cur = cur == Integer.MAX_VALUE ? -1 : cur;
		return cur;
	}

	private int x(int index) {
		return index / n;
	}

	private int y(int index) {
		return index % n;
	}

	private int ff(int from, int to, int key) {
		int ans = 0;
		Queue<Integer> queue = new LinkedList<>();
		queue.add(from);
		boolean been[] = new boolean[m * n];
		been[from] = true;
		while (!queue.isEmpty()) {
			ans++;
			int size = queue.size();
			while (size > 0) {
				int cur = queue.poll();
				int x = this.x(cur), y = this.y(cur);
				for (int i = 0; i < 8; i += 2) {
					int nextx = x + d[i], nexty = y + d[i + 1];
					// 下一个位置是有效的网格内
					if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
						int nextc = g[nextx][nexty];
						if (nextc == '#') {// 墙到不了
							continue;
						}
						int nextIndex = index(nextx, nexty);
						if (nextIndex == to) {//  到达目的地
							return ans;
						}
						// 是锁，且没有钥匙，不行。
						if (nextc >= 'A' && nextc <= 'Z' && ((key & (1 << (nextc - 'A'))) == 0)) {
							continue;
						}
						// 没去过，继续尝试
						if (!been[nextIndex]) {
							been[nextIndex] = true;
							queue.add(nextIndex);
						}
					}
				}
				size--;
			}
		}
		return -1;
	}

	@Override
	public void debug4() {
		H.compare(10, this.shortestPathAllKeys(H.str2array2("[\"@...a\",\".###A\",\"b.BCc\"]")));
		H.compare(8, this.shortestPathAllKeys(H.str2array2("[\"@.a.#\",\"###.#\",\"b.A.B\"]")));
		H.compare(6, this.shortestPathAllKeys(H.str2array2("[\"@..aA\",\"..B#.\",\"....b\"]")));
		H.compare(-1, this.shortestPathAllKeys(H.str2array2("[\"@Aa\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
